#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;

ll a[15][15];
// bool vis[15][15];
ll pre[110];
// bool previs[110];
// ll endindex;
ll ans1;
ll dp[15][15];
ll n;
void dfs(ll x,ll y,ll sum){
    // if(sum<dp[x][y])return ;
    dp[x][y]=sum;
    if(x==n-1&&y==n-1){
        ans1=sum;
        return ;
    }
    ll tx=x,ty=y+1;
    if(ty<n){
        if(sum+a[tx][ty]>dp[tx][ty]){
            pre[tx*n+ty]=x*n+y;
            dfs(tx,ty,sum+a[tx][ty]);
        }        
    }
    tx=x+1;ty=y;
    if(tx<n){
        if(sum+a[tx][ty]>dp[tx][ty]){
            pre[tx*n+ty]=x*n+y;
            dfs(tx,ty,sum+a[tx][ty]);
        } 
    }
    return ;
}

int main()
{
    IOS;
    cin>>n;
    ll x,y,c;
    while(cin>>x>>y>>c&&(x||y||c)){
        a[x-1][y-1]=c;
    }
    memset(dp,-1,sizeof(dp));
    dfs(0,0,a[0][0]);
    ll ans=ans1;
    memset(dp,-1,sizeof(dp));
    for(ll i=n*n-1;i!=0;i=pre[i]){
        ll tx=i/n;
        ll ty=i%n;
        a[tx][ty]=0;
    }
    a[0][0]=0;
    ans1=0;
    dfs(0,0,a[0][0]);
    ans+=ans1;
    cout<<ans<<endl;
    getchar();
    getchar();
    return 0;
}
